A, B, C 均为水题。。rk306，进复赛了 ~
D
D 其实也是水题，这题目是真的难懂。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;
int T, n, sx, sy, a[505][505], ans, tot;
vector<int> val;
int main() {
cin >> T;
while (T--) {
cin >> n >> sx >> sy;
rep(i, 1, n) {
rep(j, 1, n) {
scanf("%d", &a[i][j]);
}
}
ans = 1e9;
rep(i, 1, n) {
rep(j, 1, n) {
int ren = 0, rnd = 0;
rnd = (abs(i - sx) + abs(j - sy) + 1) / 2;
tot = 0;
val.clear();
rep(k, -3, 3) {
rep(l, -3, 3) {
if (abs(k) + abs(l) > 3) continue;
if (!k && !l) continue;
if (i + k < 1 || i + k > n || j + l < 1 || j + l > n) continue;
val.push_back(a[i + k][j + l]);
}
}
sort(val.begin(), val.end());
ren = 1;
int cur = 0, food = 0;
while (ren < 9) {
int tt = 8 * ren * ren;
if (food < tt) {
tt -= food;
int k = tt / cur + (tt % cur > 0);
rnd += k, food += k * cur;
}
++ren;
if (!val.size()) continue;
cur += val.back(), val.pop_back();
}
ans = min(ans, rnd);
}
}
printf("%d\n", ans);
}
return 0;
}
|
E
不是很难但理解了很久的期望题
由于 a 从外到内递减，必然会形成很多从内向外的树，所以连通块数的期望其实就是树根数的期望。
考虑每个段作为树根的贡献。
第一层是 a[i] / 2
第 i 层每个段是 (1 / a[i - 1] - 1 / a[i]) (a[i - 1] / 2) (a[i] / 2) = (a[i] - a[i - 1]) / 4
其中，1 / a[i - 1] 是上一层白块概率，但是黑块要完全待在白块里就要减去 1 / a[i]
那么如果出现只有一个点相碰的情况，这概率怎么算呢？
其实不用算它，它的概率为 0。
因为在连续空间下，计算一个子空间的概率就是在算这个空间的测度 (可以理解成一维是长度, 二维是面积, 三维是体积)
在Lebesgue测度(欧氏空间下最常用的测度定义, 我们学到的微积分基本都基于它)下，一维空间中的一个点测度就是 0
F
选点必然是从小到大选，所以可以二分最后选的点（权值最大的点），对于每块区域讨论一下（不想写，代码就让它咕咕吧（）
G
时刻具有可二分性。设二分的值为 t，容易想到对于每个格点，与每个在 t 时刻内能到达它的窗户连边，跑网络流，但是这样节点个数是 nm 级别的。考虑优化，窗户只有 6 个，那用二进制表示窗户到格点的到达状态，将状态相同的点们缩成一个点，跑最大流就好了。
H
官方题解太毒瘤，，我看的这个
时间复杂度应该是跑不满的 sqrt(n) * log(sqrt(n))
思考了一波推柿子的意义，把 sigma 化掉、去掉无效枚举状态（比如 n / d^2，d > sqrt(n) 就是无效的），判断当前柿子能否预处理。